#!/usr/bin/env python3
# -*- encoding: utf-8 -*-
"""
@UserFor     :   ***    ***
@File        :   middle-64-最短路径和.py    
@Email       :   18574945291@163.com
@Modify Time :   2021-02-15 16:36
@Author      :   code_wizard (wll) 
"""


'''
我们可以定义一个同样是二维的 dp 数组，其中 dp[i][j] 表示从左上角开始到 (i, j) 位置的最
优路径的数字和。因为每次只能向下或者向右移动，我们可以很容易得到状态转移方程 dp[i][j] =
min(dp[i-1][j], dp[i][j-1]) + grid[i][j]，其中 grid 表示原数组。
'''
class Solution:
    def minPathSum(self, grid) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # 如果是第一个格子
                if i == j == 0:
                    continue
                # 在第一行 只能从左边过来
                if i == 0:
                    grid[i][j] = grid[i][j-1]+grid[i][j]
                # 在第一列 只能从上面下来
                elif j == 0:
                    grid[i][j] = grid[i-1][j]+grid[i][j]
                # 不在第一行第一列 那么就计算
                else:
                    grid[i][j] = min(grid[i][j-1],grid[i-1][j])+grid[i][j]
        return grid[-1][-1]
    """
        因为 dp 矩阵的每一个值只和左边和上面的值相关，我们可以使用空间压缩将 dp 数组压缩为
    一维。对于第i行，在遍历到第j列的时候，因为第j-1列已经更新过了，所以dp[j-1]代表dp[i][j-1]
    的值；而 dp[j] 待更新，当前存储的值是在第 i-1 行的时候计算的，所以代表 dp[i-1][j] 的值。
    """

    def minPathSumPlus(self, grid) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i == j == 0:
                    continue
                elif i == 0:
                    grid[i][j] = grid[i][j - 1] + grid[i][j]
                elif j == 0:
                    grid[i][j] = grid[i - 1][j] + grid[i][j]
                else:
                    grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
        return grid[-1][-1]
if __name__ == '__main__':
    grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
    obj = Solution()
    print(obj.minPathSum(grid))